/*
 * @lc app=leetcode id=117 lang=cpp
 *
 * [117] Populating Next Right Pointers in Each Node II
 */
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) {
            return root;
        }
        Node *node = root;
        vector<Node *> dq;
        dq.push_back(node);

        Node *last = NULL;
        while(!dq.empty()) {
            last = NULL;
            vector<Node *> tmp;
            for (int i=0; i<dq.size(); i++) {
                if (dq[i]->left)
                    tmp.push_back(dq[i]->left);
                if (dq[i]->right)
                    tmp.push_back(dq[i]->right);
                if (last) {
                    last->next = dq[i];
                }
                last = dq[i];
                last->next = NULL;
            }
            dq = tmp;
        }
        
        return root;
    }
};
